package main

import (
	"os"
	"fmt"
)

/*读文件*/
func readMaze(filename string) [][]int{

	file, err := os.Open(filename)

	if err != nil {
		panic(err)
	}


	var row,col,end  int
	fmt.Fscanf(file, "%d	%d", &row, &col)
	fmt.Fscanf(file,"%d",&end) // 取走 6 5 之后的换行
	maze := make([][]int, row)



	for i := range maze{
		maze[i] = make([] int,col)
		for j := range maze[i] {
			fmt.Fscanf(file,"%d", &maze[i][j])
		}
		fmt.Fscanf(file,"%d",&end) // 取走 每行之后的换行
	}
	return maze
}

type point struct {
	i ,j int
}
func (p point) add(r point) point{
	return point{p.i+r.i,p.j+r.j}
}
func (p point) at (grid [][]int) (int,bool){
	// 如果行出界了 失败
	if p.i <0 || p.i >= len(grid){
		return 0,false
	}
	// 如果列出界了 失败
	if p.j < 0 || p.j >= len(grid[p.i]){
		return 0,false
	}
	// 没出界就返回这个点
	return grid[p.i][p.j],true

}
var dirs = [4]point {
	/*上左下右，注意不是坐标，i表示行 j表示列*/
	{-1,0},{0,-1},{1,0},{0,1},
}

func walk(maze [][]int,start,end point) [][]int{
	// 先建个steps来保存走的路,初始所有的值都是0,相当于maze的副本
	steps := make([][]int,len(maze))
	for i := range steps{
		steps[i] = make([]int,len(maze[i]))
	}
	// 队列，用来保存需要探索的点
	Q := []point{start}

	// 队列走完退出
	for len(Q) >0 {
		cur := Q[0]
		Q = Q[1:]

		// 发现终点退出
		if cur == end {
			break
		}

		for _,dir := range dirs {
			// 下个点
			next := cur.add(dir)

			// next点在 maze中为0， 表示不为墙 可以走
			// 并且 next在steps也为0，表示没走过 可以走
			// next != start, 满足这三个条件才可以存入steps

			val ,ok :=next.at(maze)
			// 如果出界了 或者是墙
			if !ok || val ==1{
				// 跳出去 继续探索下一点
				continue
			}
			val ,ok =next.at(steps)
			// 如果不等于0，说明已经走过了
			if !ok || val !=0 {
				// 跳出去 继续探索下一点
				continue
			}
			// 走回原点了
			if next == start {
				// 跳出去 继续探索下一点
				continue
			}

			// 开始探索

			// 经过以上的筛选，next点是可以走的，取出cur点在steps中的步数+1
			curSteps,_ :=cur.at(steps)
			steps[next.i][next.j] = curSteps+1
			// 将next点加入队列当中
			Q = append(Q, next)
		}
	}
	return steps
}

func main() {
	maze := readMaze("maze/maze.in")

	steps := walk(maze,point{0,0},point{len(maze)-1,len(maze[0])-1})
	for _,row := range steps{
		for _,val := range row{
			fmt.Printf("%5d ",val)
		}
		fmt.Println()
	}
}
